package program.linkedlist;

/**
 * 动态数据结构-链表
 */
public class LinkedList<E> {

    private class Node {
        public E data;

        public Node next;

        public Node() {
            this(null, null);
        }

        public Node(E data) {
            this(data, null);
        }

        public Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }

        @Override
        public String toString() {
            return this.data.toString();
        }
    }

    private Node head;

    private int size;

    public LinkedList() {
        this.head = null;
        this.size = 0;
    }

    /**
     * 获取链表元素个数.
     */
    public int getSize() {
        return size;
    }

    /**
     * 判断链表是否为空.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 从链表头部插入元素.
     */
    public void addFirst(E data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;

        // 上面三行代码, 可以使用下面这行代码替换.
        // head = new Node(data, head);
        size++;
    }

    /**
     * 在index位置插入新节点data.
     */
    public void add(int index, E data) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Index is error!");
        }

        if (index == 0) {
            addFirst(data);
        } else {
            Node pre = head;
            // 查找到index前一个节点.
            for (int i = 0; i < index - 1; i++) {
                pre = pre.next;
            }

            Node newNode = new Node(data);
            newNode.next = pre.next;
            pre.next = newNode;

            // 上面三行, 可以使用下面这行替换
            // pre.next = new Node(data, pre.next);
            size ++;
        }
    }

    /**
     * 从链表尾部插入元素.
     */
    public void addLast(E data) {
        if (isEmpty()) {
            addFirst(data);
        } else {
            Node pre = head;
            while (pre.next != null) {
                pre = pre.next;
            }

            pre.next = new Node(data);
            size ++;
        }
    }
}
